1. Field of the Invention
This invention relates to systems for the automated placement of labels in relation to graphical features of two- or three-dimensional drawings, either drawings produced by layout tools or drawings that in a scaled version depict "real" drawings (i.e., geographical maps and technical maps). More precisely, this invention relates to automatically producing a labeling solution for a given graph layout or map.
2. State of the Art
Graph drawing is a general area of computer science or mathematics that attempts to develop algorithms which may be used to produce aesthetically pleasing "drawings" of graphs from abstract topological information about the nodes in a graph and the edges that connect them together. A related discipline is that of graph labeling. The need for automated placement of labels in relation to graphical features first emerged from placing labels in relation to features of technical, and particularly geographical, maps. The first attempts to automate the labeling process are almost twenty years old.
In recent years, a growing recognition of a large number of applications of graph drawing have caused it to receive increased attention. Graph drawings find application in many different areas including, among others, such areas as database design (e.g, entity relationship diagrams), software engineering, CASE, software debugging, and communication networking. The labeling of the graphical features of a drawing in most of these applications is essential, since it gives important information about the relations represented by the drawing.
As used in the present specification, the term "label" is used to refer to text or other indicia to be placed on a drawing. The term "label placement" is used to refer to one or more selected areas within which a label may be placed. The term "label assignment" is used to refer to a label placement that has been chosen. Finally, the term "labeling solution" is used to refer to a set of label assignments for multiple labels such that the label placements satisfy specified criteria.
Most of the past research on the labeling problem has been done for labeling geographic and technical maps. Most prior-art techniques devised to solve the Graph Feature Label Placement (GFLP) problem are trivial in nature. Previous approaches have used greedy algorithms, exhaustive-search (backtracking) algorithms, algorithms that simulate physical models (i.e., Simulated Annealing), and reduction of the labeling problem to a variant of 0-1 integer programming. These techniques either do not produce the desired results, due to their tendency to get trapped in local optima, or they take exponential time.
Almost all of the algorithms devised to solve the GFLP problem (or a restricted version of the GFLP problem) have been focused more on the problem of labeling points and less on the problem of labeling lines.
In geographical maps, the labeling of lines (the Edge Label Placement, or ELP problem) is less restrictive than the labeling of points (Node Label Placement, or NLP problem), due to the fact that lines are usually long, and thus offer many possible positions for placing labels. The edge density of any drawing can vary. Hence, edge labeling algorithms, to be of practical importance, must perform well even for drawings with very high edge density. Since the ELP problem is NP-hard, any effective approach to solve the ELP problem must be directed toward devising heuristics for that problem.